package LeetCode._02算法基础.day12动态规划;

import org.junit.Test;
import 题组.Solution;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 23 - 20:26
 * @Description 给定一个非负整数数组 nums ，你最初位于数组的第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 * @Version 中等
 */
public class _55跳跃游戏 {
    static int[] nums = {3, 2, 1, 0, 4};
    @Test
    public void test(){
        boolean res = canJump(nums);
        System.out.println(res);
    }
    /*by me 超时*/
    public boolean canJump(int[] nums) {
        return dfs(nums, 0);
    }
    public boolean dfs(int[] nums, int index){
        if(index >= nums.length){
            return false;
        }

        if(index == nums.length - 1){
            return true;
        }

        for(int i = 1; i <= nums[index]; i++){
            if(dfs(nums, index + i)){
                return true;
            }
        }

        return false;
    }

    /*官方思路*/

    //1.贪心
    /*
    我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。
    对于当前遍历到的位置 x，如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，
    因此我们可以用 x+nums[x] 更新 最远可以到达的位置。
    在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，
    我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

     */
    public boolean canJump1(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {   //这个位置是可达的
                rightmost = Math.max(rightmost, i + nums[i]);//取最远可达位置
                if (rightmost >= n - 1) {   //可以到达最后一个位置
                    return true;
                }
            }else { //该位置已经不可达
                break;
            }
        }
        return false;
    }
}
